<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>

</body>
<script>
    // 插入排序就是当前值和前面的依次对比，比前面的小就插入进去

    /**
     * 使用插入排序算法对数组进行升序排序
     * @param {Array} arr - 待排序的数组
     * @returns {Array} 排序后的数组（原地修改）
     */
    function insertSort(arr){
        // 从第二个元素开始遍历（第一个元素视为已排序部分）
        for(let i = 1;i<arr.length;i++){
            const current = arr[i]  // 当前待插入元素
            let j = i - 1            // 指向已排序部分的最后一个元素

            // 在已排序部分中寻找插入位置：将大于current的元素后移
            while(j>=0&&arr[j]>current){
                arr[j+1] = arr[j]   // 元素右移
                j--
            }

            // 将当前元素插入正确位置
            arr[j+1] = current
        }
        return arr
    }

    const unsortedArray = [5, 3, 8, 4, 2];
    const sortedArray = insertSort(unsortedArray);
    console.log(sortedArray); // 输出: [2, 3, 4, 5, 8]
</script>
</html>